package day_2022_4_to_7.nowcoder;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 两个链表的第一个公共结点
 * @author haomin
 * @date 2022/05/07 17:30
 **/
public class FindFirstCommonNode_28f {
    // 方法一
    // 让较长的链先走k步，使得两条链长度相同，然会两条链同时向后走
    // 当遇到第一个相同节点时，该节点就是两个链表的第一个公共结点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);
        int step = Math.abs(length1 - length2);
        // 使得较长的链先走step步
        if(length2 < length1){
            for (int i = 0; i < step; i++) {
                pHead1 = pHead1.next;
            }
        }else {
            for (int i = 0; i < step; i++) {
                pHead2 = pHead2.next;
            }
        }
        // 找第一个地址相同的节点
        while (pHead1 != null && pHead2 != null){
            // 并且要保证两条链中该节点之后的所有节点值相同
            if(pHead1.val == pHead2.val && allContains(pHead1.next,pHead1.next)){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }

    // 保证两条链中该节点之后的所有节点值相同
    private boolean allContains(ListNode l1, ListNode l2) {
        while (l1 != null && l2 != null){
            if(l1.val != l2.val){
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }

    // 得到链表长度
    private int getLength(ListNode head) {
        int length = 0;
        for(ListNode x = head;x != null; x = x.next){
            length++;
        }
        return length;
    }

    // 方法二
    // 用例8/9
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        Map<Integer,Integer> map = new LinkedHashMap();
        // 使用Map，先将第一个单链表节点值全部加入到map集合
        for(ListNode x = pHead1;x != null;x = x.next){
            map.put(x.val,1);
        }
        // 然后遍历第二个单链表
        for(ListNode x = pHead2;x != null;x = x.next){
            // 将节点加入map中时，如果当前节点值已存在在map集合
            if(map.containsKey(x.val)){
                if(x.next != null){
                    // 并且在此节点之后的节点值也都在map集合之中
                    if(allContainKey(map,x.next)){
                        // 该节点有极大可能性就是pHead1和pHead2的第一个公共结点
                        return x;
                    }
                }else {
                    return x;
                }
            }
        }
        return null;
    }

    // 判断此节点之后的节点值也都在map集合之中
    private boolean allContainKey(Map<Integer, Integer> map, ListNode x) {
        while (x != null){
            if(!map.containsKey(x.val)){
                return false;
            }
            x = x.next;
        }
        return true;
    }
}